package bintree.leetcode;

/**
 * @Author: yuisama
 * @Date: 2022/9/16 14:26
 * @Description:恢复BST的两个逆序节点
 */
public class Num99_RecoverTree {
    // 莫里斯中序遍历
    public void morrisRecover(TreeNode root) {
        TreeNode x = null, y = null, tmp = null, prev = null;
        while (root != null) {
            if (root.left != null) {
                tmp = root.left;
                // 先找到左子树的最右侧节点与树根连接
                while (tmp.right != null && tmp.right != root) {
                    tmp = tmp.right;
                }
                if (tmp.right == null) {
                    // 第一次走到该节点，连接树根，继续走左子树
                    tmp.right = root;
                    root = root.left;
                } else {
                    // 当前左子树已经访问结束，继续访问右子树
                    if (prev != null && prev.val > root.val) {
                        // x只需要赋值一次
                        if (x == null) {
                            x = prev;
                        }
                        // 每当发现新的逆序对就更新y的指向，直到整个树遍历结束
                        y = root;

                    }
                    prev = root;
                    root = root.right;
                    tmp.right = null;
                }
            } else {
                // 此时左树遍历结束，判断是否存在逆序
                if (prev != null && prev.val > root.val) {
                    // x只需要赋值一次
                    if (x == null) {
                        x = prev;
                    }
                    // 每当发现新的逆序对就更新y的指向，直到整个树遍历结束
                    y = root;
                }
                prev = root;
                // 继续访问右子树
                root = root.right;
            }
        }
        if (x != null && y != null) {
            int tmpVal = x.val;
            x.val = y.val;
            y.val = tmpVal;
        }
    }

    // 上一个访问结束的节点
    TreeNode prev;
    // 当前访问节点
    TreeNode cur;
    // 在中序遍历过程中寻找逆序的两个节点x，y，且x.val > y.val
    // 在遍历过程中，当找到x节点，x就不再变化，y可以变化直到最终遍历完整个树
    TreeNode x, y;

    public void recoverTree(TreeNode root) {
        inOrder(root);
        // 当x和y不为空，说明当前树有逆序节点，交换他们的顺序
        if (x != null && y != null) {
            int tmp = x.val;
            x.val = y.val;
            y.val = tmp;
        }
    }

    public void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        // 先递归左子树
        inOrder(root.left);
        cur = root;
        if (prev == null) {
            prev = root;
        } else {
            if (prev.val > cur.val) {
                // 找到逆序对
                if (x == null) {
                    x = prev;
                }
                // 每当找到逆序对，就更新y节点的指向
                y = cur;
            }
            // 无论prev和cur的大小情况，判断后更新prev为当前节点
            prev = cur;
        }
        // 继续递归右子树
        inOrder(root.right);
    }
}
